The present invention relates generally to digital image processing and, in particular, to methods and apparatus for the digital halftoning of continuous tone images.
Digital halftoning is a technique used in image processing to produce a halftone output image from a continuous tone input image. In order to halftone a digital color image, a continuous tone color image is sampled, for example with a scanner, and the samples are then digitised and stored in a computer device. In a full color system, the digitised samples, or pixels, can consist of independent binary representation of the color components of an image. For example, in the well known red, green and blue system (RGB), utilised in most output displays, the digitised samples or pixels consist of binary representations of the red, green and blue scanned color values respectively. These binary representations typically range from 0 to 255 for each color, thereby comprising 8 bits for each primary color, or 24 bits to represent one pixel. Another color system involves cyan, magenta, yellow and black (CMYK) and is used predominantly in printer output devices.
Standard cathode ray tube (CRT) type display devices are able to display each pixel with a large number of variations of each color component of the pixel, giving rise to the desirability of storing 256 possible values for each color component of each pixel of a CRT type display. Other output devices however, such as printers and certain display devices such as ferro-electric liquid crystal displays are often designed to only be able to display a limited number of colors or intensity values for each output color, Hence, when displaying an image on such devices, it is necessary to create the sensation of multilevel colors by suitably distributing the possible output colors in the output image. By way of example, it can be assumed that each pixel of a first example display device is able to display red, green and blue color values (RGB), with each color value taking either one of a totally on or totally off state. Therefore, each color component value can display one of two colors and the total number of colors which can be displayed by such a pixel will be 2xc3x972xc3x972=8 colors.
Two well known methods of halftoning are error diffusion and dithering. To describe error diffusion and dithering, consider by way of example, a monochrome display system where each pixel of an array of pixels can display either black or white. Assume the input image has 256 possible levels of display or values, 0 through 255. A decision must be taken for each pixel whether to display an xe2x80x9coffxe2x80x9d value of 0 or xe2x80x9conxe2x80x9d value of 255.
In error diffusion for this example system, an xe2x80x9coffxe2x80x9d value is displayed at a current pixel when the input value at the pixel plus error values transferred to the pixel is less than or equal to 127, and an xe2x80x9conxe2x80x9d value is displayed when the input value plus error values transferred to the pixel are greater than or equal to 128. An error value at the current pixel is derived, being the input value at the pixel plus the error values transferred to the pixel less the chosen output value, Portions of this error value are then transferred to surrounding pixels which have not, as yet, been output, in accordance with a known distribution mask, This has the effect of spreading, or xe2x80x9cdiffusingxe2x80x9d the error over several pixels in the output image.
FIG. 25A illustrates a known error diffusion mark, where a current pixel 400 is being processed and the error value at the current pixel 400 is distributed to a limited set of neighbouring pixels 401 to 406 according to values provided by the mask. In this example, 2/8 of the error is distributed to the pixel 401 and 1/8 of the error distributed to the pixel 402, and so on.
With such arrangements, halftoning by error diffusion typically proceeds by processing pixels in raster order in the manner shown in FIG. 25B. There, a first current pixel output value is decided using an input sum for the first current pixel, in particular, a sum of the input value for the first current pixel with a weighted sum of error values of previously processed pixels. After the first current pixel output value is determined, an output sum for the first current pixel is calculated as an input sum less the current pixel output value. Note that the output sum is a weighted sum of error values of processed pixels including the first current pixel, where the error value for the first current pixel is its input value less its output value, and the weight for the first current pixel is one. The output sum is then divided into portions which are distributed to a small group of close neighbouring unprocessed pixels. That is, each portion is added to the input sum of a neighbouring unprocessed pixel. In this way, the input sum for a second current pixel is calculated as the sum of the input value for the second current pixel plus a weighted sum of error values of previously processed pixels, and the processing applied to the first current pixel can be repeated for the second current pixel.
As such, error diffusion is a neighbourhood process halftoning technique. Expressed in another way, error diffusion provides a halftone output at a pixel that depends on the halftone output of pixels in its neighbourhood. In conventional error diffusion, the error between a halftoned output value and the input value for any one pixel is typically spread amongst a neighbourhood comprising a limited number of pixels, six (6) as seen in the above example. It follows therefore that the output value of a pixel is predominantly determined by the influence of a small neighbourhood of pixels associated therewith.
It has been found that error diffusion produces-unsatisfactory results when an input image comprises video or other forms of data having motion (ie. dynamic images) or noise characteristics. When dynamic images or images having a certain associated noise therein are error diffused, the error diffusion process is subject to slight variations from one frame to the next which in turn results in pixel values begin turned xe2x80x9conxe2x80x9d and xe2x80x9coffxe2x80x9d at a detectable and distracting rate. This problem can be variously described as xe2x80x9csparkling noisexe2x80x9d, xe2x80x9cdancing dotsxe2x80x9d and xe2x80x9ctwinklingxe2x80x9d, as the effect is to produce an area having rapidly changing individual pixel values but having a substantially constant overall color. This problem applies equally to both monochrome and full color display output devices in which such images are displayed.
Further, regions of low and high intensity are typically handled poorly by traditional error diffusion. This problem may also occur in both still and moving images.
The halftoning process of dithering traditionally involves the creation of xe2x80x9cdither matrixxe2x80x9d, where the input value of a current pixel is compared with a corresponding value in the dither matrix and an output value for the current pixel is derived, For example, if the dither matrix value is less than the input value of the current pixel, the display device, such as a printer or display, produces an xe2x80x9conxe2x80x9d value at the current pixel.
A dither matrix is preferably constructed having certain characteristics which improve the appearance of output halftoned images. These characteristics include arrangement of dither matrix values so that resulting xe2x80x9conxe2x80x9d or xe2x80x9coffxe2x80x9d pixel values are as spread out as possible.
The process of dithering dynamic images, that is, dithering images forming part of an image sequence, however results in the reproduction of images have a noisy, xe2x80x9cmottledxe2x80x9d appearance in regions having a substantially constant color. Another disadvantage of dithering includes poor edge sharpness at the edges of graphical objects forming part of the image.
It is an object of the present invention to provide an alternative form of image processing which leads to improved output values for display.
In accordance with one aspect of the present invention there is disclosed a method of processing an image, said image comprising a plurality of pixels, said method comprising the steps of:
(a) determining an output value of a first current pixel, which is not at an edge of the image, using a first influence value for a first current pixel which equals a first sum, over a first set of pixels, of the product of a pixel weight value and a corresponding pixel value, where the pixel weight value is substantially equal to an weight factor raised to the power of the distance of the pixel from the first current pixel; and
(b) determining an output value for a second current pixel, using a second influence value determined as either:
(i) a product of a weight value reducing factor and the first influence value, or
(ii) a product of a weight value reducing factor and the sum of the first influence value and a value for the first current pixel,
so that the second influence value equals a second sum over a second set of pixels of the product of a pixel weight value and a corresponding pixel value, where each pixel weight value is substantially equal to a weight factor raised w the power of the distance of the pixel from the second current pixel.
In accordance with another aspect of the present invention there is disclosed a method of halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, said method comprising the steps of:
(a) determining an output value of a first current pixel, which is not at an edge of the image, using a first influence value for a first current pixel: which equals a first sum, over a first set of pixels, of the product of a pixel weight value and a corresponding pixel error value, where the pixel weight value is substantially equal to a weight factor raised to the power of the distance of the pixel from the first current pixel; and
(b) for the purpose of determining an output value for a second current pixel, calculating a second influence value for the second current pixel
(i) as a product of a weight value reducing factor and the first influence value, or
(ii) as a product of a weight value reducing factor and the sum of the first influence value and an error value for the first current pixel,
so that the second influence value equals a second sum over a second set of pixels of the product of a pixel weight value and a corresponding pixel error value, where the pixel weight value is substantially equal to a weight factor raised to the power of the distance of the pixel of the second set from the second current pixel.
In accordance with another aspect of the present invention there is disclosed a method of halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, said method comprising the steps of;
(a) determining an output value of a first current pixel, which is not at an edge of the image, using a set of two or more first influence values for a first current pixel where each first influence value equals a sum, over a first set of pixels, of the product of a pixel weight value and a corresponding pixel error value, where the pixel weight value is substantially equal to a weight factor raised to the power of the distance of the pixel from the first current pixel; and
(b) for the purpose of determining an output value for a second current pixel, calculating a set of two or more second influence values for the second current pixel where each second influence value is calculated
(i) as a product of a weight value reducing factor and one of the first influence values, or
(ii) as a product of a weight value reducing factor and the sum of one of the influences value and an error value for the first current pixel,
so that each second influence value equals a sum over a second set of pixels of the product of a pixel weight value and a corresponding pixel error value, where the pixel weight value is substantially equal to a weight factor raised to the power of the distance of the pixel of the second set from the second current pixel.
Many other aspects of the invention, including apparatus and systems are also disclosed
The present invention provides a foundation for a class of neighbourhood process halftoning methods which gather the results of halftoning from a wide neighbourhood of a current pixel, in an efficient and accurate manner.
Because these methods accurately represent the influence (or error) of halftone results in a wide neighbourbood, they exhibit improved halftone patterns in regions of low or high intensity, particularly compared to error diffusion, In such regions, an accurate value for the influence of comparatively rare exceptional valued halftone output (that is, halftone output with large error) is required.
The class of halftoning methods described herein implement a scheme for the influence of halftone output at one pixel location, on the halftone output at another location, which is described as a xe2x80x9cgeometrically reducing influencexe2x80x9d. Notably, the influence of the halftone output at one, already determined pixel, on a second, as yet undetermined pixel, reduces with the distance between the two pixels. It has been found that the rate of decrease in influence with distance can successfully be modelled, at least for substantial distances, as a geometrically reducing influencexe2x80x94that is, as an exponentially decreasing influence.
In the class of methods described herein, the geometrically reducing influence is implemented by representing the influence of the halftone output at a processed pixel on a neighbouring, as yet, unprocessed pixel, as a product of the error at the processed pixel with a weight value which equals or equals approximately, a weight factor raised to the power of the distance between the processed pixel and the unprocessed pixel.
With this representation of influence, the combined influence of previously processed pixels on a current pixel can be summarised using a small number of values either comprising or including xe2x80x9cinfluence running sumsxe2x80x9d. An influence running sum (or for brevity a xe2x80x9crunning sumxe2x80x9d) is a single value summarising the influence of a set of pixels substantially oriented in one direction from a current pixel. Once the current pixel has been determined, new running sums for use in processing subsequent pixels can be calculated efficiently using previously calculated running sums and the error at the current pixel.
This recursive calculation of running sums depends on the geometrically reducing nature of the weight values. Running sums and their recursive calculation are the mechanism for delivering the efficient and accurate representation of neighbourhood halftone influence.
In accordance with a another aspect of the present invention, there is provided a method of halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, said method comprising, for a current pixel of said image, the steps of:
(a) determining an under result and an over result for a plurality of previously halftoned pixels of said image;
(b) determining using the under result and the over result of previously halftoned pixels an under result repulsive measure and an over result repulsive measure for the current pixel;
(c) comparing the under result repulsive measure to the over result repulsive measure; and
(d) assigning a first output state value as the output value for the current pixel in the event that the under result repulsive measure is greater than the over result repulsive measure, and assigning a second output state value as the output value for said current pixel in the event that the over result repulsive measure is greater than the under result repulsive measure.
In accordance with another aspect of the present invention, there is provided a method of one or more images, each image comprising pixels, said method comprising, for each pixel of a current image, the steps of:
(a) assigning a predetermined value to an output value of the pixel,
(b) determining using the predetermined output value of the pixel a repulsive measure between the pixel and a plurality of previously halftoned pixels of the current image;
(c) comparing the repulsive measure to the minimum repulsive measure achievable for the pixel in combination with a threshold value; and
(d) retaining the predetermined value as the output value of said pixel if the repulsive measure is less than the sum of the minimum repulsive measure and the threshold value.
Apparatus for performing each of the above aspects is also disclosed.
In accordance with a another aspect of the present invention, there is provided a computer software system for executing instructions on a general purpose computer, wherein said instructions comprise a plurality of process modules for halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, said modules comprising:
a first determining module for determining an under result and an over result for a plurality of previously halftoned pixels of said image;
a second determining module for determining using the under result and the over result an under result repulsive measure and an over result repulsive measure for the current pixel:
a comparing module for comparing the under result repulsive measure to the over result repulsive measure; and
an assigning module for assigning a first output state value as the output value for the current pixel in the event that the under result repulsive measure is greater than the over result repulsive measure, and assigning a second output state value as the output value for said current pixel in the event that the over result repulsive measure is greater than the under result repulsive measure.
In accordance with a another aspect of the present invention, there is provided a computer software system for executing instructions on a general purpose computer, wherein said instructions comprise a plurality of process modules for halftoning one or more images, each image comprising a plurality of pixels, said modules comprising:
an assigning module for assigning a predetermined value to an output value of the pixel,
a determining module for determining a repulsive measure between the pixel and a plurality of previously halftoned pixels of the current image;
a comparing module for comparing the repulsive measure to the minimum repulsive measure achievable for the pixel in combination with a threshold value; and
a decision module for retaining the predetermined value as the output value of said pixel if the repulsive measure is less than the sum of the minimum repulsive measure and threshold value.
In accordance with a another aspect of the present invention, there is provided a computer system comprising:
input means for receiving an image or a sequence of images;
halftoning means for halftoning said image(s), said halftoning being characterised by a determination of the relative repulsive forces between a current pixel of the image(s) being halftoned, and a plurality of previous pixels of the image(s) that have been halftoned; and
a discrete level display for displaying the image(s) output from said halftoning means.
In accordance with a another aspect of the present invention, there is provided an image processor comprising:
input means for receiving pixel data of an image to be displayed;
means for determining repulsive measure data from repulsive forces between said pixel data and a plurality of previously halftoned pixels; and
pixel calculator means for determining halftone output data of said image processor from said pixel data and said repulsive measure data.
In accordance with a another aspect of the present invention, there is provided a method of halftoning an image, said image comprising a plurality of pixels, said method being characterised by the determination of repulsive forces between a current pixel of the image being halftoned, and a plurality of previous pixels of the image that have been halftoned.
The present inventor has named this alternative type of halftoning, Force Field Halftoning, as it relies upon relative color forces acting on a pixel.